package leetcode;
/*
思路：
不能使用乘除、取余，那么只能使用加减运算。
但是要找到一个合适的加减运算方式，不能被除数-除数一个个运算。
借助位移操作，可以最大限度完成加减运算。

被除数 / 除数= 商,任何商都可以用2进制标识。

那么被除数 = 除数 * 商的二进制标识。
结假设被除数=100，除数=10，商为10，其二进制标识为1010
那么 100 = 10 * 2^3 + 10 * 2^1 = 10 << 3 + 10 < 1

即对100而言，先找到最大的左移数，然后依次降级，直到左移数为0
 */
public class Code29 {
    public int divide(int dividend, int divisor) {
        if(dividend == 0){
            return 0;
        }

        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }

        boolean negative = (dividend ^ divisor) < 0;

        long t = Math.abs((long)dividend);
        long d = Math.abs((long)divisor);

        int result =0;

        for(int i=31;i>=0;i--){
           if((t>>i) >= d){
               result += 1>>i;
               t= t - d<<i;
           }
        }
        return negative ? -result: result;
    }
}
